package com.mapbar.ure.frontend.parser;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

import com.mapbar.ure.ASTException;
import com.mapbar.ure.ProductionType;
import com.mapbar.ure.frontend.lr1.Grammar;
import com.mapbar.ure.frontend.lr1.table.Action;
import com.mapbar.ure.frontend.lr1.table.ActionItem;
import com.mapbar.ure.frontend.lr1.table.Goto;

/**
 * 对RE直接输入的解析，生成AST，方便下一步的算法实施。
 * 
 * @author QIN Jian
 * 
 */
public class Parser<T> {

	Action action;
	Goto __goto;

	public Parser(Grammar g) {
		action = g.getAction();
		__goto = g.get__goto();
	}

	/**
	 * 是否需要使用LR(1)的解析器？理论上是不需要的吧？RE没有这么复杂？但是解析上应该是需要的。
	 * 
	 * 目前的文法如下：
	 * 
	 * RE -> RE | T
	 * 
	 * -> T
	 * 
	 * T -> T + A
	 * 
	 * -> A
	 * 
	 * A -> F *
	 * 
	 * -> F
	 * 
	 * F -> (RE )
	 * 
	 * -> available set
	 * 
	 * @param inputSequence
	 * @param k2t
	 * @return
	 * @throws ASTException
	 */
	public AST<T> parse(List<T> inputSequence, HashMap<T, ProductionType> k2t)
			throws ASTException {
		return parser(inputSequence, action, __goto, k2t);
	}

	/**
	 * AST的构建，是需要栈中存储树的构建部分。 操作应该都集中于reduce的操作。
	 * 
	 * @param inputSequence
	 * @param action
	 * @param __goto
	 * @param k2t
	 * @return
	 * @throws ASTException
	 */
	private AST<T> parser(List<T> inputSequence, Action action, Goto __goto,
			HashMap<T, ProductionType> k2t) throws ASTException {
		// initial
		Stack<ParserState<T>> stack = new Stack<ParserState<T>>();
		stack.push(new ParserState<T>(0));
		int i = 0;
		for (i = 0; i < inputSequence.size();) {
			T c = inputSequence.get(i);
			if (!k2t.containsKey(c)) {
				fail(i);
				return null;
			}
			ParserState<T> state = stack.peek();
			ProductionType word = k2t.get(c);
			ActionItem next = action.get(state.getStatus(), word);
			if (next == null) {
				fail(i);
				return null;
			}

			switch (next.type) {
			case Accept:
				return stack.peek().getAST();
			case Shift:
				AST<T> ast = new AST<T>(word, c);
				stack.push(new ParserState<T>(word, next.shiftValue, ast));
				++i;
				break;
			case Reduce:
				List<AST<T>> children = new ArrayList<AST<T>>();
				AST<T> parent;
				/**
				 * 简化ast，单一继承的就直接使用子节点。
				 */
				if (next.item.right.length == 1) {
					parent = stack.pop().getAST();
				} else {
					for (int j = 0; j < next.item.right.length; ++j) {
						children.add(stack.pop().getAST());
					}
					parent = new AST<T>(next.item.left, children);
				}
				ParserState<T> top = stack.peek();
				stack.push(new ParserState<T>(next.item.left, __goto.get(
						top.getStatus(), next.item.left), parent));
				break;
			default:
				fail(i);
				return null;
			}
		}
		/**
		 * 错误情况???
		 */
		fail(i);
		return null;
	}

	private void fail(int pos) throws ASTException {
		ASTException e = new ASTException();
		e.setErrorPosition(pos);
		throw e;
	}
}
